package com.ljy.my_study.leetcode.旋转数组的最小数字;

/**
 * @author lijunying
 * @date 2020/7/22 11:56
 */
public class TestMain {
//    把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
//    输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
//    例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  
//
//    示例 1：
//
//    输入：[3,4,5,1,2]
//    输出：1
//    示例 2：
//
//    输入：[2,2,2,0,1]
//    输出：0

    public static void main(String[] args) {
//        System.out.println(new TestMain().minArray(new int[]{2,2,2,0,1}));
//        System.out.println(new TestMain().minArray(new int[]{3,4,5,1,2}));
//        System.out.println(new TestMain().minArray(new int[]{3,5,1}));
        System.out.println(new TestMain().minArray(new int[]{3,3,4,3}));
    }

    public int minArray(int[] numbers) {
        int start=0;
        int end=numbers.length-1;
        while(true){
            int mid=(start+end)/2;
            if(start==end){
                return numbers[start];
            }
            if(start+1==end){
                return numbers[start]>numbers[end]?numbers[end]:numbers[start];
            }
            if(numbers[mid]<numbers[start]){
                end=mid;
            }else if(numbers[end]<numbers[mid]){
                start=mid;
            }else if(numbers[start]<numbers[end]){
                return numbers[start];
            }else{
                int min=numbers[start];
                for(int i=start+1;i<=end;i++){
                    if(numbers[i]<min){
                        min=numbers[i];
                        break;
                    }
                }
                return min;
            }
        }
    }

}
